//https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=23269&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13
//解法：1.二分解决；2.重要！！！

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int left = 0;
        int right = rotateArray.size() - 1;
        while(left < right){
            int mid = (left + right) / 2;
            //最小的数字在mid右边
            if(rotateArray[mid] > rotateArray[right])
                left = mid + 1;
            //无法判断，一个一个试
            else if(rotateArray[mid] == rotateArray[right])
                right--;
            //最小数字要么是mid要么在mid左边
            else
                right = mid;
        }
        return rotateArray[left];
    }
};